// 二叉树 可以用链表的节点来理解，但是树和链表是两种不同的结构
//二叉树同样每个节点只需要存储 数据（值） 和 它的子节点的引用（指针域）二叉树就是每个节点最多有两个子节点的树
/* 完全二叉树不需要存储边 因为父子节点的相对位置可以计算出来  用数组可以表示一颗完全二叉树，
完全二叉树，除了嘴底层节点没有填满，上面的都是满的， 底层的节点是都集中在左侧的位置
 这样在实际存储上一段连续的空间，但是在我们思维结构中它是一颗二叉树  */
class TreeNode {
    constructor(val){
        this.val = val 
        this.left = null
        this.right = null
    }
}
// 前序就是 根左右
function preOrder(node){
    // 一个二叉树节点如果存在那它肯定不会是原始值0 false ,不存在正常情况下应该是null,这个要看TreeNode的具体实现
    if (!node) return  
    // do something
    // console.log(node.val)
    // 
    preOrder(node.left)
    preOrder(node.right)

}
// 中序就是 左根右

function inOrder(node){
    // 一个二叉树节点如果存在那它肯定不会是原始值0 false ,不存在正常情况下应该是null,这个要看TreeNode的具体实现
    inOrder(node.left)
    if (!node) return  
    // do something
    // console.log(node.val)
    // 
    inOrder(node.right)

}
// 后序就是 左右根

function sufOrder(node){
    // 一个二叉树节点如果存在那它肯定不会是原始值0 false ,不存在正常情况下应该是null,这个要看TreeNode的具体实现
    sufOrder(node.left)
    sufOrder(node.right)
    if (!node) return  
    // do something
    // console.log(node.val)
    // 

}

// 层序遍历
// 层序遍历如果把下一层的 节点 return出去 是不是就算是转迭代了 可暂停 ，递归很多时候是不能暂停的 因为外层还没执行完 就开始执行内层
function depOrder(node){
//  需要一个辅助函数
const help = (nodes, cb)=> {
    if (!nodes || !nodes.length) return 
    const temp = [] // 用于收集下一层的节点
    for ( let node of nodes) {
        node.left && temp.push(node.left)
        node.right && temp.push(node.right)
        // do something
        // console.log(node.val);
    cb(node)
    }
    help(temp)
}
 let res =[]
 help([node], (node)=> {res.push(node.val)})
}

//计算深度 就是递归取子树深度的最大值，
function calcDepth(root){
    if (!root) return 0
    return Math.max(calcDepth(root.right), calcDepth(root.left)) +1
}

// 在计算深度的过程中可以做点别的 110平衡二叉树
var isBalanced = function(root) {
    return getDepth(root) >=0
    };
    function getDepth(root){
        if(!root) return 0
        let l = getDepth(root.left)
        let r = getDepth(root.right)
        
        // 如果子树异常把继续往外传
        if(l < 0 || r < 0){
            return -2
        }
        // -2会影响下面的差值运算 所以要先判断
        // 异常
        if (Math.abs(l -r)>1){
            return -2
        }
    
        return Math.max(l  , r) +1
    
    
    }
/* n叉树的前序遍历  关键是状态码的管理， -1根节点 n 第n个子节点 这里弹栈的条件是 n溢出children的length */
    var preorder = function (root) {
        if (!root) return []
        const res = [], s1 = [], s2 = [];
        s1.push(root);
        s2.push(-1);
    
        while (s1.length) {
            const status = s2.pop();
            const node = s1[s1.length - 1];
            switch (status) {
                case -1:
                    /* -1的下一步就是0 */
                    s2.push(0)
                    res.push(node.val);
                    break;
                default:
                    /* n的下一步就是n+1 */
    
                    if (!node.children || status >= node.children.length) {
                         s1.pop()
                        continue
                    }
                    s2.push(status + 1)
    
    
    
                    if (node.children[status]) {
    
                        s1.push(node.children[status])
                        s2.push(-1)
                    }
    
                    break;
            }
    
        }
        // console.log(res)
        return res
    
    };